Field of the Invention
The present invention generally relates to computer architectures and, more specifically, to a resource management subsystem that maintains fairness and order.
Description of the Related Art
A common practice in parallel processing systems is to design a processor that executes some number of threads simultaneously. Each thread may execute in a separate execution pipeline within the processor. As execution proceeds in parallel, different threads may request access a common resource, such as a shared memory, in a manner that may cause the threads to encounter a resource conflict. For example, multiple threads may execute a common resource access operation, such as a memory load instruction, where the multiple threads cannot simultaneously access the resource. In such a case, at least one thread is allowed to access the common resource and complete the common resource access operation. The pipeline transfers a copy of the common resource, such as one of the cache lines that some of the threads are accessing, and those threads are able to complete the common resource access operation. However, the other threads accessing the same common resource are not allowed to complete the common resource access operation and remain unserviced. Thus, some threads are allowed to complete the common resource access operation, while other threads are not. Absent a means to process multiple threads accessing a common resource, the operation is not able to complete successfully.
One approach to servicing multiple threads accessing a common resource is to allocate the resource to one or more threads until the common resource has no additional available access ports. Remaining threads accessing the same resource are placed in a pending state awaiting availability of the common resource. When the common resource has one or more available access ports, the common resource is allocated to one or more pending requests for servicing until all access ports have again been allocated. The process continues until all requests to the common resource have been serviced.
One drawback of this approach is that new requests may continue to arrive and consume access ports to the common resource while pending requests awaiting the same common resource remain unserviced. Such an occurrence, when newer requests accessing a common resource are serviced before pending requests, is called a “priority inversion.” Another drawback of this approach is that a pending request may be selected for servicing when a common resource becomes available. However, due to pipeline latency, another newer request may consume the common resource before the pending request is able to complete the common resource access operation. Yet another drawback of this approach is that a request may require access to two common resources, A and B, where A is available but B is not. The request is placed in a pending state until B becomes available. When B becomes available, the pending request is scheduled for completion. However, due to pipeline latency, another newer request may consume the A before the pending request is able to complete the common resource access operation. When newer access requests are continually allocated resources before older existing access requests, the older access requests may not be able to make forward progress and thus are not able to complete execution.
As the foregoing illustrates, what is needed in the art is a more effective way to service threads accessing a common resource.